package leetcode.array_sort;

/**
 * @author: Oliver
 * @time: 2020/6/1/22:02
 * 26. 删除排序数组中的重复项
 * <p>
 * 给定一个排序数组，你需要在 原地 删除重复出现的元素，使得每个元素只出现一次，返回移除后数组的新长度。
 * <p>
 * 不要使用额外的数组空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。
 * <p>
 * <p>
 * <p>
 * 示例 1:
 * <p>
 * 给定数组 nums = [1,1,2],
 * <p>
 * 函数应该返回新的长度 2, 并且原数组 nums 的前两个元素被修改为 1, 2。
 * <p>
 * 你不需要考虑数组中超出新长度后面的元素。
 * <p>
 * 示例 2:
 * <p>
 * 给定 nums = [0,0,1,1,1,2,2,3,3,4],
 * <p>
 * 函数应该返回新的长度 5, 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4。
 * <p>
 * 你不需要考虑数组中超出新长度后面的元素。
 * 分析：定义一个k，使得arr[l,k]存放的是不重复元素,[k+1,r]为重复元素，i指向下一个需要判断的元素 ,
 * 判断 arr[i]是否出在在 arr[l,k], 使用变量j记录当前访问到[l,k]的位置，如果都遍历完没有break，则j>k   k++，arr[k]=arr[i];
 */
class Solution26 {

    public static int removeDuplicates(int[] nums) {
        return remove(nums, 0, nums.length - 1);

    }

    private static int remove(int[] arr, int l, int r) {
        if (arr.length == 0) {
            return 0;
        }
        int k = l;//arr[l,k]  中存放不重复元素   [k+1,r]存放重复元素
        for (int i = l + 1; i <= r; i++) {//i指向下一个需要判断的元素
            int j = l;
            for (; j <= k; j++) {//每次在[l,k]区间去寻找是否出现过
                if (arr[i] == arr[j]) {
                    break;
                }
            }
            if (j > k) {
                k++;
                arr[k] = arr[i];

            }
        }
        return k - l + 1;
    }

    public static void main(String[] args) {
        int[] nums = {0, 0, 1, 1, 1, 2, 2, 3, 3, 4};
        int i = removeDuplicates(nums);
        System.out.println(i);
    }
}